// 根据一棵树的中序遍历与后序遍历构造二叉树。

// 注意:
// 你可以假设树中没有重复的元素。

// 例如，给出

// 中序遍历 inorder = [9,3,15,20,7]
// 后序遍历 postorder = [9,15,7,20,3]
// 返回如下的二叉树：

//     3
//    / \
//   9  20
//     /  \
//    15   7

#include "stdc++.h"

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 递归
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n = inorder.size();
        return buildTree(0, n - 1, 0, n - 1, inorder, postorder);
    }
    TreeNode* buildTree(int inorderLeft, int inorderRight, int postorderLeft, int postorderRight, const vector<int>& inorder, const vector<int>& postorder) {
        if (inorderLeft > inorderRight || postorderLeft > postorderRight) {
            return nullptr;
        }
        TreeNode* root = new TreeNode(postorder[postorderRight]);
        int i{inorderLeft};
        for (; i <= inorderRight; ++i) {
            if (inorder[i] == postorder[postorderRight]) {
                break;
            }
        }
        root->left = buildTree(inorderLeft, i - 1, postorderLeft, postorderLeft + i - inorderLeft - 1, inorder, postorder);
        root->right = buildTree(i + 1, inorderRight, postorderLeft + i - inorderLeft, postorderRight - 1, inorder, postorder);
        return root;
    }
};

/* 递归
中序遍历：左根右
后序遍历：左右根
时间复杂度：O(n)
空间复杂度：O(n)
*/
class Solution {
private:
    int postIndex{};
    unordered_map<int, int> indexMap{};
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // 从后序遍历的最后一个元素开始
        postIndex = postorder.size() - 1;
        // 建立（元素，下标）键值对的哈希表
        int index{0};
        for (auto& val : inorder) {
            indexMap[val] = index++;
        }
        return func(0, inorder.size() - 1, inorder, postorder);
    }
    TreeNode* func(int indexLeft, int indexRight, vector<int>& inorder, vector<int>& postorder) {
        // 如果这里没有节点构造二叉树了，就结束
        if (indexLeft > indexRight) {
            return nullptr;
        }
        // 选择postIndex位置的元素作为当前子树根节点
        int rootVal = postorder[postIndex];
        TreeNode* root = new TreeNode(rootVal);
        // 根据root所在位置分为左右两棵子树
        int index = indexMap[rootVal];
        // 下标减1
        --postIndex;
        // 构造右子树
        root->right = func(index + 1, indexRight, inorder, postorder);
        // 构造左子树
        root->left = func(indexLeft, index - 1, inorder, postorder);
        return root;
    }
};

/* 迭代
时间复杂度：O(n)
空间复杂度：O(n)
*/
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n = postorder.size();
        if (n == 0) {
            return nullptr;
        }
        auto root = new TreeNode(postorder[n - 1]);
        auto s = stack<TreeNode*>();
        s.push(root);
        int inorderIndex = n - 1;
        for (int i{n-2}; i >= 0; --i) {
            int postorderVal = postorder[i];
            auto node = s.top();
            if (node->val != inorder[inorderIndex]) {
                node->right = new TreeNode(postorderVal);
                s.push(node->right);
            } else {
                while (!s.empty() && s.top()->val == inorder[inorderIndex]) {
                    node = s.top();
                    s.pop();
                    --inorderIndex;
                }
                node->left = new TreeNode(postorderVal);
                s.push(node->left);
            }
        }
        return root;
    }
};